package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 * @Author: haogege
 * @Date: 2021/9/12
 */
public class _122_买卖股票的最佳时机II {

    public static void main(String[] args) {

        _122_买卖股票的最佳时机II v = new _122_买卖股票的最佳时机II();

        int[] ins = {1,2,3,4,5};
        System.out.println(v.maxProfit(ins));

    }

    // 动态规划解法
    public int maxProfit(int[] prices) {
        // 对于所有股票的状态，存在买和不买的关系
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][0];
    }

    // 只要当前的钱大于前面的钱，可以直接购买股票，贪心解法
    public int maxProfit4(int[] prices) {
        int total = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                total += prices[i] - prices[i - 1];
            }
        }
        return total;
    }

    public int maxProfit3(int[] prices) {
        int[][] dp = new int[prices.length][2];
        // 初始化数据
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[dp.length - 1][0];
    }

    public int maxProfit2(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }

    public int maxProfit1(int[] prices) {
        int len = prices.length;
        int[] dp = new int[len];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] <= prices[i - 1]) {
                // 小于
                dp[i] = dp[i - 1];
            } else {
                // 大于
                dp[i] = prices[i] - prices[i - 1] + dp[i - 1];
            }
        }
        return dp[len - 1];
    }

}
